package 差分Plus离散化;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.IntStream;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/5/31 16:29
 */
public class lc2251离散差分做法 {

    /*
     该题： 跟 流星 那道题 的话，对比一下，可以理解很多的东西差分相关的东西！
     主要 有两个点：
     ①：为什么 要对 离线查询的 数组 进行一个排序， 排序之后优化的点，是什么，如果不排序的话，那么,时间复杂度 会嵌套循环, 变高
     排序的话, 只需要 遍历 一遍  start有序集合, 但是不排序的话, 需要 遍历 **离线查询数组.size()** 次  start有序集合

   `②： 离散化查询求和的思想， 里面的一些 细节求前缀和的一些细节， [start, end]
    map.put(start, getOrDefault(start,0) + 1);
    map.put(end + 1, getOrDefault(start,0) - 1);  //注意这里是 end + 1, 这里是差分的一个 核心所在!
     */
    public int[] solution(int flowers[][], int person[]) {
        int plen = person.length;
        int ans[] = new int[plen];

        Map<Integer, Integer> diff = new TreeMap<>();
        // 构建差分数组
        for (int num[] : flowers) {
            diff.put(num[0], diff.getOrDefault(num[0], 0) + 1);
            diff.put(num[1] + 1, diff.getOrDefault(num[1] + 1, 0) - 1);
        }
        Integer[] st = diff.keySet().toArray(new Integer[0]);
        // 排序索引数组
        Integer[] index = IntStream.range(0, plen).boxed().toArray(Integer[]::new);
        Arrays.sort(index, (a, b) -> person[a] - person[b]);
        int i = 0, sum = 0;
        for (int idx : index) {
            while (i < st.length && person[idx] >= st[i]) {
                sum += diff.get(st[i++]);
            }
            ans[idx] = sum;
        }

        return ans;
    }


    // 因为 值域的范围比较大, 所以这里 只能使用离散化差分


    public int[] solve(int flowers[][], int persons[]) {

        TreeMap<Integer, Integer> diff = new TreeMap<>();
        //  构建差分
        for (int[] flo : flowers) {
            diff.put(flo[0], diff.getOrDefault(flo[0], 0) + 1);
            diff.put(flo[1] + 1, diff.getOrDefault(flo[1] + 1, 0) - 1);

        }
        int len = persons.length, ans[] = new int[len];
        Integer[] index = IntStream.range(0, len).boxed().toArray(Integer[]::new);

        Arrays.sort(index, (a, b) -> persons[a] - persons[b]);


        // 还是得 把差分 map 变成 entry 数组 比较好处理 些

        Map.Entry<Integer,Integer>[] entries = diff.entrySet().toArray(new Map.Entry[0]);

        int sum = 0,j = 0;
        for (int i = 0; i < len; i++) {

            while(j < entries.length &&  persons[index[i]] >= entries[j].getKey() ){
                sum += entries[j].getValue();
                j++;

            }
            ans[index[i]] = sum;
        }

        return ans;
    }


}
